//合并 K 个升序链表
//测试链接 https://leetcode.cn/problems/merge-k-sorted-lists/description/
import java.util.PriorityQueue;
public class MergeKLists {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }


        //方法一优先级队列
        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val
                    - v2.val);
            // 将所有头结点加⼊到⼩根堆中
            for (ListNode l : lists)
                if (l != null)
                    heap.offer(l);

            // 合并
            ListNode ret = new ListNode(0);
            ListNode prev = ret;
            while (!heap.isEmpty()) {
                ListNode t = heap.poll();
                prev.next = t;
                prev = t;
                if (t.next != null)
                    heap.offer(t.next);
            }

            return ret.next;
        }
    }

    //方法二递归分治
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0 , lists.length-1);
    }

    public ListNode merge(ListNode[] lists, int left, int right){
        if(left > right) return null;
        if(left == right) return lists[left];

        int mid = left + (right - left)/2;
        //[left, mid][mid+1,right]
        //合并左右两边
        ListNode list1 = merge(lists,left,mid);
        ListNode list2 = merge(lists,mid+1,right);

        //合并两个链表
        return mergeTwoList(list1, list2);
    }

    public ListNode mergeTwoList (ListNode list1, ListNode list2){
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode ret = new ListNode(0);
        ListNode cur1 = list1, cur2 = list2, prev = ret;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                prev.next = cur1;
                cur1 = cur1.next;
            }else{
                prev.next = cur2;
                cur2 = cur2.next;
            }
            prev = prev.next;
        }
        if(cur1 != null) prev.next = cur1;
        if(cur2 != null) prev.next = cur2;

        return ret.next;
    }
}